package cn.zhaoyuening.algorithms.divideandconquer;

/**
 * Created by Zhao on 2017/3/25.
 * 最大子数组
 */
public class QueryMaxSubArray {

    public static Result getMaxSubArray(Integer[] arr,int low,int high){
        if (low == high) {
            return new Result().setSum(arr[low]).setLow(low).setHigh(high);
        }
        int mid = (low+high)/2;
        //left
        Result leftResult = getMaxSubArray(arr, low, mid);
        //mid
        Result midResult = getMaxSubArray(arr, low,mid, high);
        //right
        Result rightResult = getMaxSubArray(arr, mid+1, high);
        if (leftResult.getSum()>midResult.getSum()){
            if (leftResult.getSum()>rightResult.getSum()){
                //left
                return leftResult;
            }
        }else{
            if (midResult.getSum()>rightResult.getSum()){
                //mid
                return midResult;
            }
        }
        //right
        return rightResult;
    }

    private static Result getMaxSubArray(Integer[] arr,int low,int mid,int high){
        int leftSum = Integer.MIN_VALUE;
        int leftIndex = -1;
        int rightSum = Integer.MIN_VALUE;
        int rightIndex = -1;
        //left
        for(int i=mid,sum=0;i>=low;i--){
            sum += arr[i];
            if (sum > leftSum) {
                leftSum = sum;
                leftIndex = i;
            }
        }
        //right
        for (int i=mid+1,sum=0;i<=high;i++){
            sum += arr[i];
            if (sum > rightSum) {
                rightSum = sum;
                rightIndex = i;
            }
        }
        return new Result().setHigh(rightIndex).setLow(leftIndex).setSum(leftSum+rightSum);
    }








    public static class Result{
        private int low;
        private int high;
        private int sum;

        public int getSum() {
            return sum;
        }

        public Result setSum(int sum) {
            this.sum = sum;
            return this;
        }



        public int getLow() {
            return low;
        }

        public Result setLow(int low) {
            this.low = low;
            return this;
        }

        public int getHigh() {
            return high;
        }

        public Result setHigh(int high) {
            this.high = high;
            return this;
        }

    }

}
